﻿// 0922train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <vector>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 有一组区间[a0, b0], [a1, b1], ... (a, b表示起点, 终点)
 区间有可能重叠、相邻, 重叠或相邻则可以合并为更大的区间;
给定一组连接器[x1, x2, x3, ...] (x表示连接器的最大可连接长度, 即x>= gap)
可用于将分离的区间连接起来, 但两个分离区间之间只能使用1个连接器;
请编程实现使用连接器后, 最少的区间数结果。
区间数量<10000, a,b均 <=10000
连接器数量<10000; x <= 10000

输入描述
区间组: [1,10],[15,20],[18,30],[33,40]
连接器组: [5,4,3,2]
输出描述
1
说明:
合并后: [1,10],[15,30],[33,40], 使用5, 3两个连接器连接后只剩下[1, 40]

示例 输入输出 示例仅供调试, 后台判题数据一般不包含示例
输入
[1,10],[15,20],[18,30],[33,40]
[5,4,3,2]
输出
1
说明
合并后: [1,10],[15,30],[33,40], 使用5, 3两个连接器连接后只剩下[1,40]
 */
class Solution01
{
public:
    void getIntervals(string& origin_str)
    {
        //数字，curr_num*10+ch-'0'
        //逗号并且is_left，往curr_v推curr_num
        //右括号，往curr_v推curr_num，往intervals推curr_v
        int str_size = origin_str.size();
        int curr_num = 0;
        bool is_left = false;
        vector<int>curr_v;
        for (int i=0;i< str_size; i++)
        {
            char curr_ch = origin_str[i];
            if (curr_ch=='[')
            {
                curr_v.clear();
                is_left = true;
            }
            else if (curr_ch==',')
            {
                if (is_left)
                {
                    curr_v.push_back(curr_num);
                    curr_num = 0;
                }
            }
            else if (curr_ch==']')
            {
                curr_v.push_back(curr_num);
                curr_num = 0;
                intervals_vec.push_back(curr_v);
                is_left = false;
            }
            else if (isdigit(curr_ch))
            {
                curr_num = curr_num * 10 + curr_ch - '0';
            }
            //for---
        }

        sort(intervals_vec.begin(), intervals_vec.end(), [](vector<int>&vec_1, vector<int>&vec_2)
            {
                return vec_1[0] < vec_2[0];
            });

	    //getIntervals
    }
    void getChoose(string& choose_str)
    {
        vector<int>choose_vec;
        int str_size = choose_str.size();
        if (str_size <= 2) return;
        string curr_str = choose_str.substr(1, str_size - 2);
        stringstream oh_sstream(curr_str);
        string token;

        while (getline(oh_sstream, token, ','))
        {
            choose_vec.push_back(stoi(token));
        }

        for (auto&num:choose_vec)
        {
            choose_map[num] += 1;
        }

	    //getChoose
    }

    void updateInterval(int last_i, int use_num)
    {
    	vector<vector<int>>new_intervals;
        int interval_size = intervals_vec.size();
        int new_0 = -1, new_1 = -1;
        for (int i=0; i< interval_size; i++)
        {
            if (i==last_i)
            {
                new_0 = intervals_vec[i][0];
                new_1 = intervals_vec[i + 1][1];
                vector<int>new_v = { new_0, new_1 };
                new_intervals.push_back(new_v);
                continue;
            }
            if (i==last_i+1)
                continue;

            new_intervals.push_back(intervals_vec[i]);
        }
        intervals_vec = new_intervals;

        choose_map[use_num] -= 1;
	    //updateInterval
    }

    Solution01(string&origin_str, string&choose_str)
    {
        getIntervals(origin_str);
        getChoose(choose_str);

        //区间有可能重叠、相邻, 重叠或相邻则可以合并为更大的区间
        while (true)
        {
            bool is_merge = false;
            int v_size = intervals_vec.size();
            for (int i=1; i<v_size; i++)
            {
                int last_end = intervals_vec[i - 1][1];
                int curr_start = intervals_vec[i][0];
                if (last_end>=curr_start)
                {
                    updateInterval(i - 1, -1);
                    is_merge = true;
                    break;
                }

                int min_use = INT_MAX;
                for (auto&map_item:choose_map)
                {
                    if (map_item.second == 0) continue;
                    int use_num = map_item.first;
                    if (last_end + use_num >= curr_start && use_num<min_use)
                    {
                        min_use = use_num;
                    }
                }
                if (min_use!=INT_MAX)
                {
                    updateInterval(i - 1, min_use);
                    is_merge = true;
                    break;
                }
            }

            //没有合并，打破while
            if (!is_merge) break;
            //while
        }

        cout << intervals_vec.size();
	   //Solution01 
    }
private:
    vector<vector<int>>intervals_vec;
    unordered_map<int, int>choose_map;
};


/*
小王是一名基站维护工程师，负责某区域的基站维护
某地方有 n 个基站，1 < n < 10，已知各基站之间的距离 s，0 < s < 500 
并且基站 x 到基站 y 的距离，与基站 y 到 基站 x 的距离并不一定会相同
小王从基站 0 出发，途经每个基站 1 次，然后返回基站 0 
需要请你为他选择一条距离最短的路

输入
站点数 n 和各站点之间的距离，均为整数
3     // 表示站点数
0 2 1 // 表示站点0到各站点的路程
1 0 2 // 表示站点1到各站点的路程
2 1 0 // 表示站点2到各站点的路程
输出描述
最短路程的数值

输入
3
0 2 1
1 0 2
2 1 0
输出
3
路线为0 -> 2 -> 1 -> 0，距离为所有路线最小 1 + 1 + 1 = 3
如果选择路线0 -> 1 -> 2 -> 0，距离为 2 + 2 + 2 = 6
 */
class Solution02
{
public:
    int computeTrack(vector<vector<int>>&grid)
    {
        int cost = 0;
        int v_size = track_v.size();
        for (int i=0; i< v_size-1; i++)
        {
            int r = track_v[i];
            int c = track_v[i + 1];
            cost += grid[r][c];
        }

        int first = track_v[0];
        cost += grid[0][first];
        if (track_v.size() < choose_v.size()) return cost;

        int last = track_v[v_size - 1];
        cost += grid[last][0];

        return cost;
        //computeTrack
    }

    void backTrack(vector<vector<int>>& grid, vector<bool>&used)
    {
        int curr_cost = computeTrack(grid);
        if (curr_cost >= min_result)
        {
            return;
        }

        if (track_v.size()==choose_v.size())
        {
            int cost = computeTrack(grid);
            min_result = min(cost, min_result);
            cache_v.push_back(track_v);
            return;
        }

        int v_size = choose_v.size();
        for (int i=0; i< v_size; i++)
        {
            if (used[i]) continue;

            //做选择
            track_v.push_back(choose_v[i]);
            used[i] = true;
            //回溯
            backTrack(grid, used);
            //撤销选择
            track_v.pop_back();
            used[i] = false;
        }

	    //backTrack
    }

    Solution02(vector<vector<int>>&grid, int total)
    {
        for (int i=1; i<total; i++)
        {
            choose_v.push_back(i);
        }

        int v_size = total-1;
        vector<bool>used(v_size, false);
        for (int i=0; i<v_size; i++)
        {
            //做选择
            track_v.push_back(choose_v[i]);
            used[i] = true;
            //回溯
            backTrack(grid, used);
            //撤销选择
            track_v.pop_back();
            used[i] = false;
            //for---
        }

        cout << min_result;
	    //Solution02
    }
private:
    vector<int>track_v;
    vector<int>choose_v;
    int min_result = INT_MAX;
    vector<vector<int>>cache_v;
};


/*
每种产品包含若干个型号
现某合作厂商要采购金额为 amount 元的硬件产品搭建自己的 AI 基座
假设当前库存有 N 种产品，每种产品的库存量充足，给定每种产品的价格，记为 price
（不存在价格相同的产品型号）。请为合作厂商列出所有可能的产品组合。

输入描述
输入包含采购金额 amount 和产品价格列表 price。第一行为 amount，第二行为 price

输出描述
输出为组合列表。例如：
[[500], [200, 300], [100, 200, 200], [100, 100, 300], [100, 100, 100, 200], [100, 100, 100, 100, 100]]
备注
1. 对于给定输入，产品组合少于 150 种。输出的组合为一个数组，数组的每个元素也是一个数组，表示一种组合方案。如果给定产品无法组合金额为 amount 元的方案，那么返回空列表。
2. 两种组合方案，只要存在一种产品的数量不同，那么方案认为是不同的。
3. 每种产品型号价格不相同

输入
500
100, 200, 300, 500
输出
[[100, 100, 100, 100, 100], [100, 100, 100, 200], [100, 100, 300], [100, 200, 200], [200, 300], [500]]
 */
class Solution03
{
public:
    void initData(string& origin_str)
    {
        origin_str += ',';
        int curr_num = 0;
        for (auto&oh_char:origin_str)
        {
            if (isdigit(oh_char))
            {
                curr_num = curr_num * 10 + oh_char - '0';
            }
            else if (oh_char==',')
            {
                choose_v.push_back(curr_num);
                curr_num = 0;
            }
        }

        //initData
    }

    void backTrack(int start)
    {
        int curr_sum = accumulate(track_v.begin(), track_v.end(), 0);
        if (curr_sum == sum_limit_)
        {
            result.push_back(track_v);
        }
        if (curr_sum >= sum_limit_) return;

        int v_size = choose_v.size();
        for (int i=start; i< v_size; i++)
        {
            track_v.push_back(choose_v[i]);
            backTrack(i);
            track_v.pop_back();
        }

	    //backTrack
    }

    Solution03(string&origin_str, int limit)
    {
        sum_limit_ = limit;
        initData(origin_str);
        backTrack(0);

        cout << '[';
        int result_size = result.size();
        for (int r=0; r<result_size; r++)
        {
            int item_size = result[r].size();
            cout << '[';
            for (int c=0; c<item_size; c++)
            {
                cout << result[r][c];
                if (c!=item_size-1)
                {
                    cout << ',' << ' ';
                }
            }
            cout << ']';
            if (r != result_size - 1)
            {
                cout << ',' << ' ';
            }
        }
        cout << ']';
	    //Solution03
    }
private:
    int sum_limit_ = 0;
    vector<int>choose_v;
    vector<int>track_v;
    vector<vector<int>>result;
};

/*
给定参数 n ，从 1 到 n 会有 n 个整数 1，2，3，...，n
这 n 个数字共有n!种排列，按大小顺序升序列出所有排列情况，并一一标记
当 n = 3 时，所有排列如下："123","132","213","231","312","321"
给定 n 和 k 返回第 k个排列

输入
第一行为 n
第二行为 k
n 的范围是 1 ~ 9
k 的范围是 1 ~ n!

输出
输出排列第 k 位置的数字

输入
3
3
输出
213
 */
class Solution04
{
public:
    void backTrack(vector<bool>&used)
    {
        if (is_find) return;
        if (track_v.size()== choose_v.size())
        {
            string num_str;
            for (auto&num:track_v)
            {
                num_str += to_string(num);
            }
            result.push_back(stoi(num_str));
            if (result.size()== target_i+1)
            {
                is_find = true;
            }

            return;
        }

        int v_size = choose_v.size();
        for (int i=0; i<v_size; i++)
        {
            if (used[i]) continue;
            //做选择
            used[i] = true;
            track_v.push_back(choose_v[i]);
            //回溯
            backTrack(used);
            //撤销选择
            used[i] = false;
            track_v.pop_back();
        }

        //backTrack
    }
    Solution04(int num, int k)
    {
        //按大小顺序升序
        for (int i=1; i<=num; i++)
        {
            choose_v.push_back(i);
        }
        target_i = k - 1;

        int v_size = choose_v.size();
        vector<bool>used(v_size, false);
        for (int i=0; i< v_size; i++)
        {
            //做选择
            used[i] = true;
            track_v.push_back(choose_v[i]);
            //回溯
            backTrack(used);
            //撤销选择
            track_v.pop_back();
            used[i] = false;
        }

        cout << result[target_i];

	    //Solution04
    }
private:
    bool is_find = false;
    int target_i = -1;
    vector<int>track_v;
    vector<int>choose_v;
    vector<int>result;
};

/*
小杨申请了一个保密柜，但是他忘记了密码
只记得密码都是数字，而且所有数字都是不重复的

请你根据他记住的数字范围和密码的最小数字数量，帮他算下有哪些可能的组合，
规则如下：
1. 输出的组合都是从可选的数字范围中选取的，且不能重复；
2. 输出的密码数字要按照从小到大的顺序排列，密码组合需要按照字母顺序，从小到大的顺序排序
3. 输出的每一个组合的数字的数量要大于等于密码最小数字数量；
4. 如果可能的组合为空，则返回"None"

输入描述
1. 输入的第一行是可能的密码数字列表，数字间以半角逗号分隔
2. 输入的第二行是密码最小数字数量

输出描述
可能的密码组合，每种组合显示成一行，每个组合内部的数字以半角逗号分隔，从小到大的顺序排列
输出的组合间需要按照字典序排序。比如：2,3,4 放到 2,4 的前面

输入
2,3,4
2
输出
2,3
2,3,4
2,4
3,4
最小密码数量是两个，可能有三种组合：2,3、2,4、3,4；三个密码有一种：2,3,4
 */
class Solution05
{
public:
    void backTrack(vector<int>& num_vec, int start)
    {
        if (track_v.size()>=length_)
        {
            result.push_back(track_v);
        }

        int v_size = num_vec.size();
        for (int i=start; i<v_size; i++)
        {
            track_v.push_back(num_vec[i]);
            backTrack(num_vec, i + 1);
            track_v.pop_back();
        }

	    //backTrack
    }
    Solution05(vector<int>&num_vec, int length)
    {
        length_ = length;
        sort(num_vec.begin(), num_vec.end());

        int v_size = num_vec.size();
        for (int i=0; i<v_size; i++)
        {
            track_v.push_back(num_vec[i]);
            backTrack(num_vec, i + 1);
            track_v.pop_back();
        }

        if (result.empty())
        {
            cout << "None";
            return;
        }

        sort(result.begin(), result.end(), [](vector<int>&vec_1, vector<int>&vec_2)
            {
                int v_size = min(vec_1.size(), vec_2.size());
                for (int i=0; i<v_size; i++)
                {
                    if (vec_1[i] < vec_2[i])
                    {
                        return true;
                    }
                    if (vec_1[i]>vec_2[i])
                    {
                        return false;
                    }
                }
                return vec_1.size() < vec_2.size();
            });

        int result_size = result.size();
        for (int r=0; r< result_size; r++)
        {
            int item_size = result[r].size();
            for (int c=0; c< item_size; c++)
            {
                cout << result[r][c];
                if (c!=item_size-1)
                {
                    cout << ',';
                }
            }

            if (r!=result_size-1)
            {
                cout << '\n';
            }
        }

	    //Solution05
    }
private:
    vector<int>track_v;
    int length_ = 0;
    vector<vector<int>>result;
};

int main()
{
	{
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        vector<int>num_vec;
        while (getline(oh_sstream, token, ','))
        {
            num_vec.push_back(stoi(token));
        }

        int length;
        cin >> length;

        Solution05 solu(num_vec, length);

        return 0;
	}
	{
        int num, k;
        cin >> num >> k;
        Solution04 solu(num, k);

        return 0;
	}
	{
        int limit;
        string limit_str;
        getline(cin, limit_str);
        limit = stoi(limit_str);

        string origin_str;
        getline(cin, origin_str);

        Solution03 solu(origin_str, limit);

        return 0;
	}

	{
        int g_size;
        cin >> g_size;

        vector<vector<int>>grid(g_size, vector<int>(g_size));

        for (int r=0; r<g_size; r++)
        {
            for (int c=0; c<g_size; c++)
            {
                cin >> grid[r][c];
            }
        }

        Solution02 solu(grid, g_size);
        return 0;
	}
    string intervals_str;
    string choose_str;
    cin >> intervals_str >> choose_str;

    Solution01 solu(intervals_str, choose_str);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
